package 链表和树.二叉树;
//Java：二叉树展开为链表
public class FlattenBinaryTreeToLinkedList{
    public static void main(String[] args) {
        Solution solution = new FlattenBinaryTreeToLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
class Solution {
//方法一：采用头插法构建链表  按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树，才能实现这个顺序？
//步骤
//按照右子树 - 左子树 - 根的顺序 DFS 这棵树就是倒着的先序遍历。所以采取头插法，如果当前节点为空，返回。
//递归右子树。
//递归左子树。
//把 root.left 置为空。
//头插法，把 root 插在 head 的前面，也就是 root.right=head。
//现在 root 是链表的头节点，把 head 更新为 root。
private TreeNode head;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = head; // 头插法，相当于链表的 root.next = head第一次head = null
        //后续不断的使新的节点right执向head以后更新head
        head = root; // 现在链表头节点是 root
    }
    //方法二：分治
}
//leetcode submit region end(Prohibit modification and deletion)

}